package fun.ticsmyc.graph;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * 拓扑排序的时间复杂度和空间复杂度都是 O(M+N)
 * @author Ticsmyc
 * @package fun.ticsmyc.graph
 * @date 2021-02-17 16:42
 */
public class 拓扑排序 {


    /**
     * 207. 课程表
     * 使用BFS完成拓扑排序
     * @param numCourses
     * @param prerequisites
     * @return
     */
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] indegrees =  new int[numCourses];//入度
        int[][] adjacency = new int[numCourses][numCourses]; //邻接表
        Deque<Integer> queue = new LinkedList<>(); //入度为0的点

        //统计入度和邻接表
        for(int[] cp : prerequisites){
            indegrees[cp[0]]++;
            adjacency[cp[1]][cp[0]]++;
        }

        //所有度为0的点进队列
        for(int i=0;i<indegrees.length;++i){
            if(indegrees[i] ==0){
                queue.offer(i);
            }
        }

        //度0的点相连的点 度-1， 如果度为0 入队列
        int cnt=0;
        while(!queue.isEmpty()){
            int cur = queue.poll();
            cnt++;
            for(int i=0;i<numCourses;++i){
                if(adjacency[cur][i]!=0){
                    --indegrees[i];
                    if(indegrees[i]==0){
                        queue.offer(i);
                    }
                }
            }
        }
        return numCourses==cnt;
    }


    /**
     * 207. 课程表
     * 使用DFS完成拓扑排序  主要是标志的设置
     * @param numCourses
     * @param prerequisites
     * @return
     */
    public boolean canFinish2(int numCourses, int[][] prerequisites) {
        List<List<Integer>> adjacency = new ArrayList<>();
        for(int i=0;i<numCourses;++i){
            adjacency.add(new ArrayList<>());
        }

        int[] flags = new int[numCourses];

        for(int[] cp : prerequisites){
            adjacency.get(cp[1]).add(cp[0]);
        }

        for(int i=0;i<numCourses;++i){
            if(!dfs(adjacency,flags,i)){
                return false;
            }
        }
        return true;
    }

    /**
     未被访问 flag=0
     被当前节点出发的dfs访问  flag=1
     被其他节点出发的dfs访问 flag=-1
     */
    private boolean dfs(List<List<Integer>> adjacency, int[] flags, int i){
        if(flags[i] ==1) return false;
        if(flags[i]==-1) return true;
        flags[i]=1;
        for(int j: adjacency.get(i)){
            if(!dfs(adjacency,flags,j)) return false;
        }
        flags[i]=-1;
        return true;
    }
}
